package xyf.p02.stack_queue;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * ClassName: J059_QueueMax
 * Description:
 * Author: xyf
 * Date: 9/7/22 7:49 PM
 * Version: 1.0
 **/
public class J059_QueueMax
{
    class MaxQueue
    {
        Queue<Integer> queue;

        Deque<Integer> maxQueue;

        public MaxQueue()
        {
            queue = new LinkedList<>();
            maxQueue = new LinkedList<>();
        }

        public int max_value()
        {
            if (maxQueue.isEmpty())
            {
                return -1;
            }
            return maxQueue.peekFirst();
        }

        public void push_back(int value)
        {
            while (!maxQueue.isEmpty() && maxQueue.peekLast() < value)
            {
                maxQueue.pollLast();
            }
            maxQueue.offerLast(value);
            queue.offer(value);
        }

        public int pop_front()
        {
            if (queue.isEmpty())
            {
                return -1;
            }
            int num = queue.poll();
            if (!maxQueue.isEmpty() && maxQueue.peekFirst() == num)
            {
                maxQueue.pollFirst();
            }
            return num;
        }
    }
}